﻿/*
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]

	3
   / \
  9  20
	/  \
   15   7
返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

	   1
	  / \
	 2   2
	/ \
   3   3
  / \
 4   4
返回 false 。
*/

#include "AllInc.h"

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
public:
	bool isPerfactBalance(TreeNode* root, int& depth)
	{
		if (NULL == root)
		{
			depth = 0;
			return true;
		}
		int leftdepth, rightdepth;
		bool bleft = isPerfactBalance(root->left, leftdepth);
		bool bright = isPerfactBalance(root->right, rightdepth);
		depth = max(leftdepth, rightdepth) + 1;
		return bleft && bright && abs(leftdepth - rightdepth) < 2;
	}

	bool isBalanced(TreeNode* root) 
	{
		int depth = 0;
		return isPerfactBalance(root, depth);
	}
};

//int main()
//{
//	TreeNode n1(1);
//	TreeNode n2(2);
//	TreeNode n3(3);
//	TreeNode n4(4);
//	TreeNode n5(5);
//	n1.left = &n2;
//	n1.right = &n3;
//	n3.left = &n4;
//	n3.right = &n5;
//
//	Solution s;
//	auto result = s.isBalanced(&n1);
//
//	return 0;
//}